package com.company.ljh.sort;

import java.util.Random;

/**
 * @description: 快排
 * @projectName:leet_code
 * @see:com.company.ljh.sort
 * @author:ljh
 * @createTime:2023/7/6 18:19
 * @version:1.0
 */
public class FastSort {
    public static void main(String[] args) {
        int[] ints = {3, 2, 1, 5, 6, 4};
        partition(ints,0,5);
        System.out.println(ints);
    }
    /**
     * 快速排序
     * 思路：选取一个数，小于该数的放前面，大于该数的放后面
     */
    private static Random random = new Random(System.currentTimeMillis());
    //1.循环遍历，效率低
    private static void partition(int[]nums,int start,int end){

        //随机选取一个数当作比较数
        int pivot = start + random.nextInt(end - start +1);
        //将pivot放置到第一位，方便交换
        swap(nums,start,pivot);
        //同时将pivot指向最开始
        pivot = 0;
        //从第二位开始遍历
        int index = start+1;
        int right = end;
        //左右指针，指向当前交换的数
        while(pivot < right){
            if(nums[index] <= nums[pivot]){
                //小于等于当前数，放左边
                swap(nums,index++,pivot++);
            }else{
                //放右边,右指针前移一位，当前指针不变
                swap(nums,index,right--);
            }
        }

        if(start < pivot-1){
            //两边元素分别递归
            partition(nums,start,pivot-1);
        }
        if(pivot+1 <end) {
            partition(nums, pivot + 1, end);
        }

    }

    /**
     * 优化法，维护左右指针，左右指针数据进行交换
     * @param nums
     * @param start
     * @param end
     */
    public static void fastSort(int nums[],int start,int end){
        //随机选取一个下标
        int pivot = (int) (start + (Math.random() * (end - start + 1)));

        int pivotNum = nums[pivot];
        int left = start - 1;
        int right = end + 1;
        while(left < right){
            //当前数小于，因此跳过
            do {
                left++;
            }
            while(nums[left] < pivotNum);
            do {
                right--;
            }
            while(nums[right] > pivotNum);

            if(left < right){
                swap(nums,left,right);
            }
        }
        if(right > start){
            fastSort(nums,start,right);
        }
        if (right + 1 < end){
            fastSort(nums,right + 1,end);
        }
    }

    private static void swap(int [] nums,int index1,int index2){
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}
